COMMENT ⊗   VALID 00002 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	\magnification\magstephalf
C00007 ENDMK
C⊗;
\magnification\magstephalf
\input macro.tex
\def\today{\ifcase\month\or
  January\or February\or March\or April\or May\or June\or
  July\or August\or September\or October\or November\or December\fi
  \space\number\day, \number\year}
\baselineskip 14pt
\rm
\line{\sevenrm a42.tex[154,phy] \today\hfill}

\bigskip
\line{\bf Homework Solution. See Hopcroft and Ullman, Ex.~3.20.\hfill}

Let $Q=\{1,2,\ldots,n\}$, $S=\{1\}=F$.
Let $\Sigma=\{a↓T\}\cup\{b↓q\}$, where $a↓T$ has transition relation
$\{1\}\times T$, for all $T\subseteq Q$, $b↓q$~has transition relation
$\{\langle q,1\rangle\}$, for all $q\in Q$. There are $2↑{|Q|}$ characters~$a↓T$.
If $T≠T'$, some state belongs to only one of $T$ and~$T'$, say $q\in T$
and $q\notin T'$. Then $a↓Tb↓q\in L$, $a↓{T'}b↓q\notin L$, so
$a↓T\not\sim a↓{T'}$ and they must go to distinct states of a DFM.
There are $2↑{|Q|}$ distinct~$a↓T$, so the number of states is at least
that great. The construction of DFMs from NFMs never requires more than
$2↑{|Q|}$~states, so $f(n)=2↑n$.

The way the above solution was invented went like this. The construction
of a DFM from an NFM gives me $2↑{|Q|}$ states, but in general some
can't be reached from the start state, and some are equivalent. If I~can
avoid those difficulties I~get $2↑Q$~reachable inequivalent states, all 
of which remain when the machine is minimized. To make them all reachable,
for each state $T\subseteq Q$ of the DFA I~want some string to take start
state~$\{1\}$ to~$T$. A~single character~$a↓T$ will do, if its transition
relation in the DFA takes~1 to the states in~$T$. To make them all
inequivalent, for any two states~$T$ and~$T'$ there must be a string that
distinguishes them. Two sets, such as~$T$ and~$T'$, differ by there being
an element of one, say~$q$, that's not in the other; say $q\in T$,
$q\notin T'$. So I~want some string to take every set that contains~$q$
(even just~$\{q\}$) to a set that contains~1, and no set that doesn't
contain~$q$ to a set that contains~1. That is, the transition relation
of the string must contain $\langle q,1\rangle$ and no $\langle q',1\rangle$
with $q'≠q$. A~single character~$b$ will do, if its transition relation
is $\{\langle q,1\rangle\}$.

A puzzle for those so inclined: how many characters must an $n$-state NFA
have, if the transtion relations of its strings include all relations
$\subseteq Q\times Q$?



\bigskip
\parindent0pt
\copyright 1986 Robert W. Floyd
First draft (not published)
May 6, 1986.
%revised date;
%subsequently revised.

\bye